package com.gwcloud.leetcode.offers;

import java.util.HashSet;

/** 
* @ClassName   : Leetcode0380 
* @author      : ganwei 
* @date        : 2020年6月4日 
* @Description : TODO 
*/
public class Leetcode0380 {
	HashSet<String> hset = new HashSet<String>();
    /**
     * -解题思路，
     */
	public String[] permutation(String s) {
		
		backtrace(s, new StringBuilder(), new boolean[s.length()]);
		
		String[] result = new String[hset.size()];
		hset.toArray(result);
		return result;
		
    }
	
	public void backtrace(String s, StringBuilder sb, boolean[] visited) {
		if(sb.length() == s.length()) {
			hset.add(sb.toString());
		}
		
		for(int i = 0; i < s.length(); i++) {
			if(visited[i]) {
				continue;
			}
			
			visited[i] = true;
			sb.append(s.charAt(i));
			
			backtrace(s, sb, visited);
			
			sb.deleteCharAt(sb.length()-1);
			visited[i] = false;
		}
		
	}
	
    /**
     * -主函数
     */
    public static void main(String[] args) {
    	Leetcode0380 l0380 = new Leetcode0380();
    	l0380.permutation("abc");
    }
}
